Obeleži sve kategorije koje odgovaraju problemu

Постоји \(n\) локација на \(x\)-оси на које је могуће поставити предајник. На располагању су два предајника са дометом \(d\). Потребно је поставити их тако да буду што више размакнути како би покривеност била што већа, али и да буду на раздаљини највише \(d\) како би могли међусобно да комуницирају. Написати програм који одређује максималну раздаљину између предајника. Временска сложеност треба да буде \(O(n \log n)\), а просторна \(O(n)\).

Улаз

Са стандардног улаза се уноси број \(n\) (\(n \leq 10^5\)) и затим се уноси \(n\) целих бројева из интервала \([-10^9, 10^9]\) који представљају координате тачака на \(x\)-оси где је могуће сместити предајнике. На крају се уноси број \(d\) (\(d \leq 10^9\)).

Излаз

На стандардни излаз исписати један број који представља тражену раздаљину.

Пример

Улаз

4
7 3 1 8
3

Излаз

2